/***************************************************************************
*                                                                          *
*   Fachhochschule Koeln                                 Matthias Gross    *
*   Nachrichtentechnik                                          SS 1998    *
*                                                                          *
*   Demo-Programm fuer den Aufbau eines Syntaxbaumes                       *
*                                                                          *
***************************************************************************/

#include "ableit.h"                     /* Eigenes Header-Files einbinden */

char *Operatoren="+-*/^";               /* Die im Programm verwendeten Operatoren
                                           in der richtigen Reihenfolge */

char *TestInput="((x+2-3+7+ 0*x) )";    /* Der Test fuer das Programm...  */

int StrAnalyse(char *str)
/* Diese Routine liefert zurueck:
     1 falls str eine Zahl ist,
     0 falls unbekannt
*/
{
  int  i;

  if (str!=NULL)
  {
    for (i=strlen(str)-1;i>=0;i--)
      if (!isdigit(str[i]) && str[i]!='.' && str[i]!=' ')
                                        /* Keine Ziffer oder Lücke */
        break;
    if (i<0)
      return 1;      /* Es ist eine Zahl! */
  }
  return 0;
}

char *StrFindEK(char *str)
/* Die Routine findet im String str zu einer oeffnenden Klammer ( an
   der ersten Position des Strings die Position der passenden schliessenden Klammer )
   Liefert NULL, falls String fehlerhaft ist.
*/
{
  char *estr = str;  /* Der Zeiger auf die schliessende Klammer         */
  int   KZ=0;        /* Zaehler fuer oeffnende und schließende Klammern */

  if (str != NULL && str[0]=='(')
                     /* Gueltiger String? und erstes Zeichen ( ?        */
    while(*(++estr) != '\0')
    {
      if (*estr=='(')  /* Weitere ( geht auf */
        KZ++;
      if (*estr==')')  /* Klammer ) geht zu  */
        KZ--;
      if (KZ<0)      /* Hier steht estr auf der passenden schliessenden ) */
        break;
    }
  if (KZ>=0)         /* Fehlerhafte Eingabe oder fehlende ) Klammer */
    estr=NULL;
  return estr;
}

char *StrClean(char *str)
/* Entfernt bei einem String fuehrende und anhaengende Luecken
   und entfernt ggfs. ueberfluessige Klammern am Ende und Beginn.
   Diese Funktion wird an Ort und Stelle im Speicher durchgefuehrt.
   Liefert NULL, falls String zusammengesetzt ist.
   Die Routine wird rekursiv verwendet.
*/
{
  char *s1=str, *s2=str;  /* Zwischenspeicher um str nicht zu aendern */

  if (str)                                  /* Ist es ein String? */
  {
    while (*s2!='\0') s2++;                 /* Zeiger ans Ende setzen */
    s2--;
    while (s2>=str && *s2==' ') *s2--='\0'; /* Ende trimmen (\0 neu setzen) */

    s2=str;
    while (*s2==' ') s2++;                  /* Beginn trimmen */
    if (s2 != str)                          /* Falls Zeichen am Anfang, str nach vorne kopieren */
      while ( (*s1++ = *s2++) != '\0');
    s1=s2=str;
    while (*s2!='\0') s2++;                 /* Zeiger zur Pruefung ans Ende */
    s2--;
    if (*s1=='(')
      if (StrFindEK(s1)==s2)                /* String ist math. OK */
      {
        *s1=*s2=' ';                        /* () entfernen    */
        StrClean(str);                      /* Nochmals Clean ausfuehren! */
      }
      else
       return NULL;                         /* String ist math. nicht OK */
  }
  return str;
}

MathNode *NewNode(char *str)
/* Neues Knotenelement mit dem Inhalt str generieren.
   Es wird entsprechender Platz angefordert und str ggfs umkopiert
   oder math. korrekt eingesetzt.
   Falls Routine scheitert, wird NULL zurueckgegeben.
*/
{
  MathNode   *MN;                /* Zeiger auf den neuen Knoten */

  MN = (MathNode *)malloc(sizeof(MathNode));
                                 /* Platz fuer Knoten schaffen und Zeiger speichern */
  if (MN!=NULL)
  {
    MN->left = MN->right = NULL; /* Zu Beginn ist kein Nachfolger vorhanden */
    MN->Op='\0';                 /* Kein Operator */
    MN->Wert = 0.0;              /* Wert ist 0    */
    MN->Text=NULL;               /* String ist leer */
    if (str!=NULL)               /* Uebergebenen String math. korrekt speichern */
    {
      StrClean(str);            /* Zunaechst str mal bereinigen */

/*... evtl Fehlerwert beruecksichtigen ...*/

      if (StrAnalyse(str)==1)   /* Ist es nur noch eine Zahl?   */
        sscanf(str, "%lf", &(MN->Wert)); /* Dann nur die Zahl speichern. */
      else
      {                         /* sonst den kompletten Text ablegen */
        MN->Text = (char *)malloc(strlen(str)+1);
        if (MN->Text)           /* Platz ist da, also ablegen */
          strcpy(MN->Text, str);
/*... evtl Fehlerwert beruecksichtigen ...*/
      }
    }
  }
  return MN;
}

MathNode *DelTree(MathNode *MN)
/* Loescht den gesamten Teilbaum auf den MN zeigt und liefert NULL zurueck.
*/
{
  if (MN!=NULL)
  {
    DelTree(MN->left);    /* Erstmal links und rechts loeschen */
    DelTree(MN->right);
    free(MN->Text);       /* Jetzt gespeicherten Text freigeben */
    free(MN);             /* Jetzt den Knoten selber freigeben */
  }
  return NULL;
}

MathNode *SetWert(MathNode *MN, double w)
/* Setzt Knoten MN auf Wert w und loescht anhaengenden
   linken und rechten Teilbaum.
   (Dies wird beim Kuerzen des Baums verwendet)
*/
{
  MN->left  = DelTree(MN->left);    /* Erstmal links und rechts loeschen */
  MN->right = DelTree(MN->right);
  free(MN->Text);                   /* Eigenen Text entfernen */
  MN->Text=NULL;                    /* Und Zeiger auf NULL setzen! */
  MN->Op='\0';
  MN->Wert=w;                       /* Wert eintragen! */
  return MN;
}

MathNode *SimplifyTree(MathNode *MN)
/* Vereinfacht den eingegebenen Syntaxbaum mit der Wurzel MN
   z.Z. werden hier beruecksichtigt:
-  Zusammenfassen von Zahlen bei +, -, *, /, ^
-  0 + ? wird zu ?
-  0 * ?, 0 / ?, 0 ^ ? wird zu 0
-  1 * ? = ?, 1 ^ ? = 1
Weitere Moeglichkeiten:
-  ? + 0 wird zu ?  Wie loest man soetwas mit den obigen Faellen?
-  ? * 0 wird zu 0
-  x * x zu x^2 oder sogar x*x*x... zu x^n
*/
{
  MathNode *MNT;

  if (MN!=NULL && MN->Op!='\0')   /* Standard-Paerorderverfahren ansetzen */
                                  /* Blaetter nicht beruecksichtigen */
  {
    SimplifyTree(MN->left);       /* Zunaechst links und rechts vereinfachen */
    SimplifyTree(MN->right);

    if (MN->left->Op=='\0' && MN->left->Text==NULL && /* Eine Zahl steht links! */
        MN->right->Op=='\0' && MN->right->Text==NULL) /* und eine Zahl rechts!  */
    {                             /* Wert berechnen und Baum kuerzen            */
      switch (MN->Op)             /* Zunaechst Wert bestimmen                   */
      {
        case '+':
          SetWert(MN,MN->left->Wert+MN->right->Wert);
          break;
        case '-':
          SetWert(MN,MN->left->Wert-MN->right->Wert);
          break;
        case '*':
          SetWert(MN,MN->left->Wert*MN->right->Wert);
          break;
        case '/':
          SetWert(MN,MN->left->Wert/MN->right->Wert);
          break;
        case '^':
          SetWert(MN,pow(MN->left->Wert,MN->right->Wert));
          break;
      }
    }
    else if (MN->left->Op=='\0' && MN->left->Text==NULL && MN->left->Wert==0)
                                        /* Eine 0 ist links! */
    {
      if (MN->Op=='+')                  /* Der Fall 0 + ? */
      {
        MNT=MN->right;                  /* Merken */
        free(MN->Text);                 /* Text leeren */
        DelTree(MN->left);              /* Links die 0 loeschen */
        *MN = *MNT;                     /* Rechten Ast hochkopieren */
        free(MNT);                      /* Ueberfluessigen Knoten loeschen */
      }
      else if (MN->Op=='*' || MN->Op=='/' || MN->Op=='^')
                                        /* Die Faelle 0 * ?, 0 / ? = 0 oder 0 ^ ? = 0 */
        SetWert(MN,0.0);                /* Also Knoten auf 0 und Rest loeschen */
    }
    else if (MN->left->Op=='\0' && MN->left->Text==NULL && MN->left->Wert==1)
                                        /* Eine 1 ist links! */
    {
      if (MN->Op=='*')                  /* Der Fall 1 * ? = ? */
      {
        MNT=MN->right;                  /* Merken */
        free(MN->Text);                 /* text leeren */
        DelTree(MN->left);              /* Links die 1 loeschen */
        *MN = *MNT;                     /* Rechten Ast hochkopieren */
        free(MNT);                      /* Ueberfluessigen Knoten loeschen */
      }
      else if (MN->Op=='^')             /* Der Fall 1 ^ ? = 1 */
        SetWert(MN,1.0);                /* Also Knoten auf 1 und Rest loeschen */
    }
  }
  return MN;
}

MathNode *SplitNode(MathNode *MN)
/* Splittet den vorhandenen Baum im Praeorderverfahren auf
*/
{
  char *t1;         /* Zeiger auf Trennstelle im InputString */
  int   i=0;        /* Zaehler fuer Operatoren, Start bei +  */

  if (MN!=NULL)     /* Ist es ein Knoten?  */
  {
    if (MN->Text != NULL && MN->Op=='\0')
                          /* Ist da noch neuer Text zu interpretieren? */
    {
      do
        if (t1=strchr(MN->Text, Operatoren[i]))   /* Ist ein +, - ... da? */
/* ...Die Bestimmung von t1 ist hier sehr naiv vorgenommen worden.
   Bitte zusaetzlich Klammern beruecksichtigen!...
*/
        {
          MN->right=NewNode(t1+1);      /* Linken Teil eintragen! */
          *t1='\0';                     /* Text splitten          */
          MN->left=NewNode(MN->Text);   /* Rechten Teil eintragen! */
          MN->Op=*t1=Operatoren[i];     /* Operator eintragen, String wieder restaurieren */
          break;                        /* Fertig! */
        }
      while (Operatoren[++i]!='\0');    /* Alle Operatoren abgehen */
    }
    SplitNode(MN->left);    /* Nun den linken und rechten Ast auch splitten */
    SplitNode(MN->right);
  }
  return MN;
}

void OutputInfix(MathNode *MN)
/* Ausgabe des Baums in Inorder-Technik (Infix-Notation)
*/
{
  if (MN!=NULL)
  {
    OutputInfix(MN->left);
    if (MN->Op != '\0')
      printf("%c ", MN->Op);
    else if (MN->Text != NULL)
      printf("%s ", MN->Text);
    else
      printf("%lf ", MN->Wert);
    OutputInfix(MN->right);
  }
}

void OutputInfixKlammer(MathNode *MN, char Op)
/* Ausgabe des Baums in Inorder-Technik (Infix-Notation) mit korrekter Klammerung.
   Op ist der Operator des uebergeordneten Knotens
*/
{
  int K = 0;       /* Sollen Klammern gesetzt werden? 0=Nein */
  if (MN!=NULL)
  {
    switch(Op)     /* Muss eine Klammer gesetzt werden? */
    {
      case '^': if (MN->Op!='\0') K = 1; /* Falls Operator da ist () setzen */
                break;
      case '*': case '/':
                if (MN->Op=='+' || MN->Op=='-') K=1
                break;
      /* Im Default-Fall bleibt K = 0 */
    }
    if (K) printf("(");
    OutputInfixKlammer(MN->left, MN->Op);
    if (MN->Op != '\0')
      printf("%c ", MN->Op);
    else if (MN->Text != NULL)
      printf("%s ", MN->Text);
    else
      printf("%lf ", MN->Wert);
    OutputInfixKlammer(MN->right, MN->Op);
    if (K) printf(")");
  }
}

void OutputPostfix(MathNode *MN)
/* Ausgabe des Baums in Postorder (UPN-Notation)
*/
{
  if (MN!=NULL)
  {
    OutputPostfix(MN->left);
    OutputPostfix(MN->right);
    if (MN->Op != '\0')
      printf("%c ", MN->Op);
    else if (MN->Text != NULL)
      printf("%s ", MN->Text);
    else
      printf("%lf ", MN->Wert);
  }
}

/*--- Das Hauptprogramm zum Testen ---*/
void main()
{
  MathNode *MN;             /* Der Syntaxbaum */

  MN = NewNode(TestInput);  /* Wert an oberstem Knoten eintragen */
  SplitNode(MN);            /* Und Syntaxbaum erstellen */
  OutputInfix(MN);          /* Mal ausgeben */
  printf("\n");
  OutputInfixKlammer(MN, '\0'); /* Mal ausgeben mit Klammern */
  printf("\n");
  OutputPostfix(MN);
  printf("\n");

  SimplifyTree(MN);         /* Syntaxbaum vereinfachen */
  OutputInfix(MN);          /* Und wieder ausgeben */
  printf("\n");
  OutputPostfix(MN);
  printf("\n");
}